package org.hot100.h146;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author yu
 * @Date 2022/3/2
 */
public class LRUCache2 {

    public static void main(String[] args) {

    }

    private Map<Integer, Node2> map = null;
    private DoubleList2 doubleList2 = null;
    private Integer cap;

    public LRUCache2(int capacity) {

        map = new HashMap<>();
        doubleList2 = new DoubleList2();
        cap = capacity;

    }

    public int get(int key) {

        if (!map.containsKey(key)) {
            return -1;
        }

        Node2 node2 = map.get(key);
        put(node2.k, node2.v);

        return node2.v;
    }

    public void put(int key, int value) {

        Node2 node2 = new Node2(key, value);

        if (map.containsKey(key)) {

            // 如果 map 中已经存在该值，doubleList2 删除 对应的数据，再添加
            doubleList2.remove(node2);
            doubleList2.addFirst(node2);
            map.put(key, node2);
        } else {

            if (cap == doubleList2.getSize()) {
                Node2 removeLast = doubleList2.removeLast();
                map.remove(removeLast.k);
            }
            doubleList2.addFirst(node2);
            map.put(key, node2);
        }

    }

}

class DoubleList2 {

    private Node2 head, tail;

    private int size;

    public void addFirst(Node2 node2) {

        if (head == null) {
            head = tail = node2;
        } else {
            Node2 n = head;
            n.prev = node2;
            node2.next = n;
            head = node2;
        }
        size++;

    }

    public void remove(Node2 node2) {

        if (head == node2 && tail == node2) {
            head = null;
            tail = null;
        } else if (tail == node2) {
            node2.prev.next = null;
            tail = node2.prev;
        } else if (head == node2) {
            node2.next.prev = null;
            head = node2.next;
        }

        size--;
    }

    public Node2 removeLast() {

        Node2 n = tail;
        remove(tail);
        return n;
    }

    public int getSize() {
        return size;
    }
}

class Node2 {

    Node2 next, prev;
    int k, v;

    public Node2(int k, int v) {
        this.k = k;
        this.v = v;
    }
}